﻿#include <iostream>
using namespace std;

#define  NUM 6+2
#define MAX_PATH 100
struct Node
{
	int key;
	int flag;//获得当前节点的范围索引
	Node()
	{
		flag = 0;
	}
};

class Graph
{
public:
	//stack<int> searchStack;
	int resultPath[MAX_PATH][NUM];
	int result[NUM + 1];//将result设为NUM+1，主要是为了避免发生B->D->B的事情

	Node headNode;//起始节点
	Node endNode;//终止节点
	int pathNum;
	int nPos;
	bool Mark[NUM];

public:
	Graph()
	{
		//将矩阵中的元素置为空
		for (int i = 0; i < NUM; i++)
		{
			for (int j = 0; j < MAX_PATH; j++)
			{
				resultPath[j][i] = 0;
			}
			result[i] = 0;

			Mark[i] = false;
		}
		result[NUM] = 0;
		pathNum = 0;
		nPos = 0;
	}

	void test()
	{
		//对应无向图的矩阵
		int Matrix[NUM][NUM] = {
			{0,1,0,1,0,0,0,0}, //A
			{1,0,1,1,0,0,0,0},//B
			{0,1,0,0,1,0,0,0},//C
			{1,1,0,0,1,1,0,0}, //D
			{0,0,1,1,0,0,1,0},  //E
			{0,0,0,1,0,0,1,1},  //F
			{0,0,0,0,1,1,0,0},  //G
			{0,0,0,0,0,1,0,0}  //H
		};
		//开始节点
		headNode.key = 1;
		headNode.flag = 1;

		//结束节点
		endNode.key = 5;

		FindAllPath(Matrix, headNode, endNode);
		cout << "路径数目为：" << pathNum << endl;
		for (int i = 0; i < pathNum; i++)
		{
			cout << "第" << i << "条: ";
			for (int j = 0; j < NUM; j++)
			{
				if (resultPath[i][j] == 0)
				{
					break;
				}
				cout << resultPath[i][j] << "  ";
			}
			cout << endl;
		}
		int i = 0;

	}

	/************************************************************************/
	/* 函数功能：找到图中两个节点之间的所有路径
	   参数说明：1、Matrix   初始矩阵，将路径矩阵的形式存储，本程序对应的是一个无向图。
				 2、headNode 初始节点
				 3、endNode  结束节点
		主要的思想  利用深度优先遍历的算法
	 1、利用result来存放每次从栈中出栈的数据，里面很可能就是要找的路径，为什么要单独提取出来，因为包含了多条路径
	 2、通过设置 访问是否的变量来避免回路/
	/************************************************************************/
	void FindAllPath(int Matrix[NUM][NUM], Node startNodeKey, Node endNodeKey)
	{
		result[nPos] = startNodeKey.key;  //将当前元素放入结果集中
		Mark[startNodeKey.key - 1] = true;  //将访问标记为已访问
		nPos++;  //结果集索引加1
		while (nPos != 0)
		{
			int tempVal = result[nPos - 1];//获取到最前面的元素  
			if (tempVal == endNodeKey.key)  //若当前元素为目标节点
			{
				for (int j = 0; j < nPos; j++)
				{
					resultPath[pathNum][j] = result[j];  //将结果集复制于最后的路径矩阵中
				}
				nPos--;  //回溯至上一个节点
				result[nPos] = 0;  //结果集对应索引置为空
				pathNum++;  //路径数目加1
				Mark[endNodeKey.key - 1] = false;
				break;
			}
			while (startNodeKey.flag < NUM)//利用flag来指示每次的元素的索引  
			{
				if (Matrix[tempVal - 1][startNodeKey.flag] == 1)
				{
					if (Mark[startNodeKey.flag] == false)//利用Mark来判断是否已经访问过该节点  
					{
						Node tempNode;
						tempNode.key = startNodeKey.flag + 1;
						FindAllPath(Matrix, tempNode, endNodeKey);//深度优先遍历算法，  
					}
				}
				startNodeKey.flag++;//索引值相应的加一  
			}

			if (startNodeKey.flag == NUM)//如果已经是到最后的邻居，说明访问结束，  
			{                           //将对应的值置为空  
				nPos--;  //再次向上回溯
				startNodeKey.flag = 0;  //将节点的索引置为空
				result[nPos] = 0;  //将结果集中对应的索引置为空
				Mark[startNodeKey.key - 1] = false;  //访问之后标记为未访问。因为下面的元素已经访问结束，便于下次的访问
				break;
			}
		}
	}
};